{
  // 链表是由一系列节点组成的集合，每个节点都使用一个对象引用指向它的后继（指向后面一个节点位置），
  // 而指向另一个节点的引用叫链，链表几乎可以用在任何可以使用的一维数组的地方，链表插入和删除效率是比较高的，
  // 除了对数据的随机访问。像在JS中数组是一个对象与其它语言相比效率低了很多，我们可以考虑用链来代替它。
  // 单项链表
  // function LinkedList() {
  //   // 辅助类，表示要加入链表的项
  //   var Node = function (element) {
  //     this.element = element;
  //     element.next = null; // 指向链表中下一个节点的指针
  //   };
  //   // 链表长度
  //   var length = 0;
  //   // 链表头部
  //   var head = null;
  //   // 项链表尾部添加一项
  //   this.append = function (element) {
  //     var node = new Node(element);
  //     var current;
  //     if (head === null) {
  //       // 链表为空，添加到首部
  //       head = node;
  //     } else {
  //       current = node;
  //       // 循环链表, 直到找到最后一项
  //       while (current.next) {
  //         current = current.next;
  //       }
  //       // 找到最后一项，将其next赋值为node，简历连接
  //       current.next = node;
  //     }
  //     length++;
  //   };
  //   // 从链表中移除一项
  //   // 在普通链表中：链表最后一个节点的下一个元素始终是null。
  //   this.removeAt = function (position) {
  //     // 检查是否越界
  //     if (position > -1 && position < length) {
  //       var current = head,
  //         previous,
  //         index = 0;
  //       if (position === 0) {
  //         //移除第一项
  //         head = current.next;
  //       } else {
  //         while (index++ < position) {
  //           previous = current;
  //           current = current.next;
  //         }
  //         // 将previous与current的下一项链接起来，跳过current，从而移除它
  //         previous.next = current.next;
  //       }
  //       length--;
  //       return current.element;
  //     } else {
  //       return null;
  //     }
  //   };
  //   // 向链表特定位置插入一项 插入成功返回true，失败返回false
  //   this.insert = function (position, element) {
  //     //检查是否越界
  //     if (position >= 0 && position <= length) {
  //       var node = new Node(element),
  //         current = head,
  //         previous,
  //         index = 0;
  //       if (position === 0) {
  //         //在第一个位置添加
  //         node.next = current;
  //         head = node;
  //       } else {
  //         while (index++ < position) {
  //           previous = current;
  //           current = current.next;
  //         }
  //         //通过改变指针，将node链接在previous和current之间
  //         node.next = current;
  //         previous.next = node;
  //       }
  //       length++;
  //       return true;
  //     } else {
  //       return false;
  //     }
  //   };
  //   // 从链表中移除一项
  //   this.remove = function (element) {
  //     let index = this.indexOf(element);
  //     return this.removeAt(index);
  //   };
  //   // 返回元素在链表中的索引，没有返回-1
  //   this.indexOf = function (element) {
  //     var current = head;
  //     var index = 0;
  //     while (current) {
  //       if (current.element === element) {
  //         return index;
  //       }
  //       index++;
  //       current = current.next;
  //     }
  //     return -1;
  //   };
  //   // 判断链表是否为空
  //   this.isEmpty = function () {
  //     return length === 0;
  //   };
  //   // 返回链表元素个数
  //   this.size = function () {
  //     return length;
  //   };
  //   // 返回链表第一个元素
  //   this.getHead = function () {
  //     return head;
  //   };
  //   // 只输出元素的值
  //   this.toString = function () {
  //     var current = head;
  //     var str = '';
  //     while (current) {
  //       str + ',' + current.element;
  //       current = current.next;
  //     }
  //     return str.slice(1);
  //   };
  //   // 打印元素的值
  //   this.pring = function () {
  //     console.log(this.toString());
  //   };
  // }

  // 单项链表
  function Node(element) {
    this.element = element;
    this.next = null;
  }
  function LinkedList() {
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
  }
  function find(item) {
    var currNode = this.head;
    while (currNode.element !== item) {
      currNode = currNode.next;
    }
    return currNode;
  }
  function insert(newElement, item) {
    var newNode = new Node(newElement);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
  }
  function display() {
    var currNode = this.head;
    while (currNode.next !== null) {
      console.log(currNode.next.element);
      currNode = currNode.next;
    }
  }
  function findPrevious(item) {
    var currNode = this.head;
    while (currNode.next !== null && currNode.next.element !== item) {
      currNode = currNode.next;
    }
    return currNode;
  }
  function remove(item) {
    var prevNode = this.findPrevious(item);
    var currNode = this.find(item);
    if (prevNode.next !== null) {
      prevNode.next = currNode.next;
      prevNode.next = null;
    }
  }

  var nodes = new LinkedList();
  nodes.insert('first', '1');
  nodes.insert('second', '2');
  nodes.insert('third', '3');
  nodes.display();
  console.log('=======');
  nodes.remove('2');
  nodes.display();
}
